package top.ddltech.algorithm.search;

import top.ddltech.algorithm.util.Queue;
import top.ddltech.algorithm.util.SequentialSearch;

/**
 * 基于拉链法的散列表
 */
public class SeparateChainingHash<Key, Value> {

    // 键值对总数
    private int N;
    // 散列表的大小
    private int M;
    // 存放链表对象的数组
    private SequentialSearch<Key, Value>[] st;

    public SeparateChainingHash() {
        this(997);
    }

    public SeparateChainingHash(int M) {
        // 创建M条链表
        this.M = M;
        st = (SequentialSearch<Key, Value>[]) new SequentialSearch[M];
        for (int i = 0; i < M; i++) {
            st[i] = new SequentialSearch();
        }
    }

    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }

    private Value get(Key key) {
        return (Value) st[hash(key)].get(key);
    }

    public void put(Key key, Value val) {
        st[hash(key)].put(key, val);
    }

    public Iterable<Key> keys() {
        Queue<Key> queue = new Queue<Key>();
        for (int i = 0; i < M; i++) {
            for (Key key : st[i].keys()) {
                queue.enqueue(key);
            }
        }
        return queue;
    }
}
